package org.leetcode.easy.leetcode101;

import org.leetcode.TreeNode;

import javax.print.DocFlavor;
import java.util.*;

public class Solution
{




    public boolean isSymmetric2(TreeNode root)
    {
        boolean isSame = compare(root.left, root.right);

        return isSame;
    }


    private boolean compare(TreeNode left,TreeNode right)
    {
         if (left==null && right==null )
         {
             return true;
         }

         if (left!=null && right==null)
         {
             return false;
         }

         if (left==null && right!=null )
         {
             return false;
         }

         if (left.val!=left.val)
         {
             return false;
         }

         //判断外侧
        boolean outside = compare(left.left,right.right);

         //判断内侧
        boolean inside = compare(left.right,right.left);

        boolean isSame = outside && inside;

        return isSame;

    }



    /**
     * 错误，当root为 [1,2,2,null,3,null,3]
     */
    public boolean isSymmetric(TreeNode root) {

        if (root==null)
        {
            return true;
        }

        Deque<TreeNode> deque = new LinkedList<>();

        if (root.right!=null){deque.add(root.right);}
        if (root.left!=null){deque.add(root.left);}


        while (!deque.isEmpty())
        {
            int length = deque.size();

            if (length%2!=0) return false;

            Stack<Integer> stack = new Stack<>();

            while (length>0)
            {
                TreeNode tempNode = deque.pop();

                if (!stack.isEmpty() && stack.peek()==tempNode.val)
                {
                    stack.pop();
                }else {
                    stack.push(tempNode.val);
                }

                if (tempNode.right==null)
                {
                    deque.add(new TreeNode(-1));
                }else {
                    deque.add(tempNode.right);
                }

                if (tempNode.left==null)
                {
                    deque.add(new TreeNode(-1));
                }else {
                    deque.add(tempNode.left);
                }

                length--;
            }

            if (stack.size()>0)
            {
                return false;
            }

        }

        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode leftLeaf = new TreeNode(3);
        TreeNode rightLeaf = new TreeNode(3);

        // 创建中间层节点
        TreeNode leftMid = new TreeNode(2, null, leftLeaf);
        TreeNode rightMid = new TreeNode(2, null, rightLeaf);

        // 创建根节点，使得整个二叉树对称
        TreeNode root = new TreeNode(1, leftMid, rightMid);


        boolean symmetric = solution.isSymmetric2(root);
        System.out.println(symmetric);

    }
}
